#ifndef _HASH_H_
#define _HASH_H_


/**********************************
write by zhangliang <liangzhws@foxmail.com>
**********************************/


#ifndef NULL

#define NULL     0

#endif

#ifndef __BOOL
#define __BOOL

typedef int bool;

#define false    0
#define true     1

#endif

#ifndef _INIT_HEAD
#define _INIT_HEAD

#define init_head(type, head) init_head_##type(head)

#endif

#ifndef __ENTRY
#define __ENTRY

#define entry(ptr, type, member) (type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))

#endif
/***************************************
hash model:
          ------
         | head |
          ------\
                 \
                  > ------------------            ----------
                   | hash unit pointer|-->...--> | hash unit|
                    ------------------            ----------
                   | heah unit pointer|-->NULL
                    ------------------
                     .
                     .
                     .
                    ------------------            -----------
                   | hash unit pointer|-->...--> | hash unit |
                    ------------------            -----------
***************************************/

#define _HASH_KEY_T

typedef long hash_key_t;

#ifndef INVAILD_KEY
#define INVAILD_KEY  -1
#endif

#define _HASH_S
#define _HASH_T

typedef struct hash_s {
	hash_key_t key;
	struct hash_s * next;	
} hash_t;


typedef unsigned long ( * hash_op ) (hash_key_t key, unsigned long);

#define _HASH_HEAD_S
#define _HASH_HEAD_T

unsigned long hash_op_def(hash_key_t key, unsigned long n); 

#define HASH_OP_DEF     hash_op_def
#define HASH_OP_NULL    (hash_op)-1

typedef struct hash_head_s {
	hash_t ** phash;	
	unsigned long n;
	hash_op  op;	
} hash_head_t; 

#define init_head_hash_head_t(head) do {     \
	(head)->phash = NULL;                \
	(head)->n = 0;                       \
	(head)->op = HASH_OP_DEF;            \
	} while (0)

/**
  @name: hash_set_space
  @function: init hash head, and give a little hash unit to hash_head_t management
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #void * buf# alloc memory for store units potiner
  @param: #unsigned long size# the size is times of sizeof(hash_t *) 
  @return: #void#
  @algorithm complexity: O(n) , n is the size/sizeof(hash_t *)
*/
void hash_set_space(hash_head_t * head,void * buf, unsigned long size);

/**
  @name: set_hash_function
  @function: change hash function the manager(hash head) of hash units   
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #const hash_op * pfunc# new hash function
  @return: #hash_op# return old hash function
  @algorithm complexity: O(1)
*/
hash_op hash_set_function( hash_head_t * head, const hash_op pfunc);

/**
  @name: hash_is empty
  @function: jugde hash head is empty or not
  @param: #hash_head_t * head# hash head who is manager of hash unit
  @return: #bool# true is empty , false is not empty
  @algorithm complexity: O(1) 
*/
bool hash_is_empty(const hash_head_t * head);

/**
  @name: hash_empty
  @function: clear the units of the head, after invoke it , means the hash head manage noting hash units
  @param: #hash_head_t * head# hash head who is manager of hash unit
  @return: #void#
  @algorithm complexity: O(1)
*/
void hash_empty(hash_head_t * head); 

/**
  @name: hash_set_key
  @function: set the hash unit's key value, key value  must be set  
  @param: #hash_t * unit# hash unit
  @param: #hash_key_t * key# the key value of hash unit
  @return: #void#
  @algorithm  complexity: O(1)
*/
void hash_set_key(hash_t * unit, hash_key_t key);

/**
  @name: hash_get_key
  @function: get the hash unit's key value, key value must be set  
  @param: #hash_t * unit# hash unit
  @return: #hash_key_t# hash unit's key
  @algorithm complexity: O(1)
*/
hash_key_t hash_get_key(const hash_t * unit);

/**
  @name: hash_add
  @function: add one hash unit to hash head who is hash unit manager
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #hash_t * unit# hash unit
  @return: #void#
  @algorithm complexity: O(1)
*/
void hash_add(hash_head_t * head, hash_t * unit);

/**
  @name: hash_del
  @function: del one hash unit from hash head who is hash unit manager
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #hash_t * unit# hash unit poninter point to one entry of hash unit
  @return: #void#
  @algorithm complexity:O(1)
*
void hash_del(hash_head_t * head, hash_t * unit); 

/**
  @name: hash_del_by_key
  @function: del hash unit from hash head who is hash unit manager rely on hash key
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #hask_key_t key # hash key
  @return: #void#
  @algorithm complexity: O(1)
*/
void hash_del_by_key(hash_head_t * head, hash_key_t key);

/**
  @name: hash_find_count
  @function: calculate the number of hash unit who key values equel key in hash head
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #hash_key_t key# hash key value of hash unit
  @return: #unsigned long# the number of hash unit who has key value equel the param2
  @algorithm complexity:O(1) 
*/
unsigned long hash_find_count(hash_head_t * head, hash_key_t key); 

/**
  @name: hash_find
  @function: get the hash unit in hash head who is hash unit manager
  @param: #hash_head_t * head# hash head who is hash unit manager
  @param: #hash_key_t key# hash key who is one part of hash unit
  @param: #unsigned index# the same hask key in hash head may be more than one ,so index is represent which one you want to get, index begin 0
  @return: #const hash_t *# hash unit pointer point to one hash unit , NULL is represent noting match the key in hash head or index not matching
  @algorithm complexity:O(1)
*/
const hash_t * hash_find(hash_head_t * head, hash_key_t key, unsigned long index);

/**
  @name: hash_is_exist
  @function: judge unit in hash head or not
  @param: #const hash_head_t * head# hash head
  @param: #const hash_t * unit# hash unit
  @return: #bool# true is exist and false isn't exist
  @algorithm complexity: O(1)
*/
bool hash_is_exist(const hash_head_t * head, const hash_t * unit);

#endif /* _HASH_H_ */
